/**
 * @param {string} s
 * @return {string[][]}
 */
var partition = function (s) {
    let res = [], path = [];
    dfs(s, 0)
    return res

    function dfs(s, startIndex) {
        // 终止条件
        if (startIndex >= s.length) {
            res.push([...path])
            return
        }
        // 单层递归逻辑
        for (let i = startIndex; i < s.length; i++) {
            // 判断是否是回文数，不是就继续，知道切割到是回文数
            if (!isPalindrome(s, startIndex, i)) continue
            // 切割[startIndex, i]的字母，会多切一个所以结尾要到i - startIndex + 1
            let str = s.substr(startIndex, i - startIndex + 1)
            path.push(str)
            dfs(s, i + 1) //递归 不能重复切割，所以i+1
            path.pop() // 回溯
        }
    }
    // 双指针法判断回文数
    function isPalindrome(s, l, r) {
        for (let i = l, j = r; i < j; i++, j--) {
            if (s[i] !== s[j]) return false;
        }
        return true;
    }
};
